package company.tree;

/**
 * 1569. 将子数组重新排序得到同一个二叉搜索树的方案数
 *
 * 给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉搜索树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉搜索树与 nums 原本数字顺序得到的二叉搜索树相同。
 *
 * 比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。
 *
 * 请你返回重排 nums 后，与原数组 nums 得到相同二叉搜索树的方案数。
 * 输入：nums = [2,1,3]
 * 输出：1
 * 解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。
 *
 *
 * 输入：nums = [3,4,5,1,2]
 * 输出：5
 * 解释：下面 5 个数组会得到相同的 BST：
 * [3,1,2,4,5]
 * [3,1,4,2,5]
 * [3,1,4,5,2]
 * [3,4,1,2,5]
 * [3,4,1,5,2]
 *
 *
 * 由于答案可能会很大，请将结果对 10^9 + 7 取余数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-ways-to-reorder-array-to-get-same-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 思路分析
 * 1、新构成的2叉树路径得和之前的一致
 */
public class NumOfWays1569 {
    public static void main(String[] args) {

    }
}
